Generally speaking, in systems using public key cryptography, each party is associated with both a private and a public key. The public keys are known publicly, or are available from a Certificate Authority. To sign a message, a signer uses its private key. Because the signer's private and public keys are related, a verifier may then verify the signature using the signer's public key. Because the signer's private key is known only to the signer (and perhaps to a private key generator, or PKG), third parties are not able to forge the signer's signature.
The various embodiments of the present invention also are compatible with identity-based signature schemes. Roughly speaking, identity-based signature schemes are public key schemes in which the public key of an entity is derived from information associated with the entity's identity. For instance, the identity information may be personal information (i.e., name, address, email address, etc.), or computer information (i.e., IP address, etc.). In addition, identity information may include not only information that is strictly related to an entity's identity, but also widely available information such as the time or date. That is, the importance of the concept of identity information is not its strict relation to the entity's identity, but that the information is readily available to anyone who wishes to encrypt a message to the entity.
An entity's private key in an identity-based system using public key cryptography is generated and distributed by a trusted party or logical process, typically known as a private key generator (“PKG”). The PKG uses a master secret to generate private keys. Because an entity's public key may be derived from its identity, when Bob wants to verify a signature from Alice, he does not need to retrieve Alice's public key from a database. Instead, Bob merely derives the key directly from Alice's identifying information. Databases of public keys are unnecessary. Certificate authorities (“CAs”) also are unnecessary. There is no need to “bind” Alice's identity to his public key because his identity is his public key.
The concept of identity-based systems is not new. It was proposed in A. Shamir, Identity-Based Cryptosystems and Signatures Schemes, ADVANCES IN CRYPTOGRAPHY—CRYPTO '84, Lecture Notes in Computer Science 196 (1984), Springer, 47-53. However, practical identity-based signature schemes have not been found until recently.
Public key and identity-based systems have been further expanded by incorporating a hierarchical structure. For instance, identity-based schemes involve a hierarchy of logical or actual PKGs. A root PKG may issue private keys to other PKGs, who in turn may issue private keys to users in particular domains. This enables a verifier to verify a signature from a signer without an online lookup of the signer's public key or lower-level public parameters, even if the verifier is not in the system at all, as long as the verifier obtained the public parameters of the root PKG. Another advantage of a hierarchical identity-based signature scheme is damage control. For instance, disclosure of a domain PKG's secret would not compromise the secrets of higher-level PKGs, or of any other PKGs that are not direct descendents of the compromised domain PKG.
Although known public key and identity-based systems have provided schemes for generating and verifying digital signatures, the known signature schemes have had significant shortcomings. For instance, multisignature schemes have not enabled multiple signers to sign multiple documents. A multisignature scheme that enabled multiple signers to sign multiple documents would increase the efficiency of the signature even further. For instance, such a multisignature could be used to compress a certificate chain. Accordingly, there is a need for a signature scheme that allows multiple signers to sign multiple documents together.
There also is a need for ring signature schemes for identity-based systems using public key cryptography. Ring signatures were recently introduced in R. Rivest, A. Shamir, Y. Tauman, How to Leak a Secret, ADVANCES IN CRYPTOLOGY—ASIACRYPT 2001, Lecture Notes in Computer Science 2248 (2001), Spring, 552. Ring signatures enable a member of a group (not necessarily established a priori) to sign a message such that a third party can verify that some member of the group created the signature but cannot determine which member. However, efficient ring signature schemes have not been available for identity-based encryption schemes. Accordingly, there is a need for identity-based ring signature schemes.
There also is a need for proxy signatures, proxy decryption, delegation, and electronic voting in hierarchical identity-based systems using public key cryptography. Such features were proposed for non-hierarchical systems in P. Horster, H. Petersen, Self-Certified Keys—Concepts and Applications, PROC. 3 OF CONF. ON COMMUNICATIONS AND MULTIMEDIA SECURITY, 1997. However, these features have not been available for hierarchical systems. Accordingly, there is a need for hierarchical identity-based signature schemes that enable proxy signatures, proxy decryption, delegation, and electronic voting.
There also is a need for more efficient hierarchical identity-based signature schemes that enable a portion of the signature to be generated offline. For many applications, the online signing time is more important than the total signing time. In these cases, the efficiency of the scheme can be increased by enabling more of the signature and verification algorithms to be performed offline. Online/offline signature schemes were proposed in A. Shamir, Y. Tauman, Improved Online/Offline Signature Schemes, ADVANCES IN CRYPTOLOGY—CRYPTO 2001, Lecture Notes in Computer Science 2139 (2001), Springer, 355-367. However, online/offline signature schemes have not been available for hierarchical identity-based systems. Accordingly, there is a need for efficient online/offline hierarchical identity-based signature schemes.
It is therefore an object of the present invention to provide a multisignature scheme that allows multiple signers to sign multiple documents. It is another object of the present invention to provide an identity-based ring signature scheme. It is a further object of the present invention to provide a hierarchical identity-based signature scheme that enables proxy signatures, proxy detection, delegation, and electronic voting. It is a still further object of the present invention to provide an efficient online/offline hierarchical identity-based signature scheme.